/**
 * AVL树
 * @param <AnyType>
 */
public class AvlTree<AnyType extends Comparable> {
    public class AvlNode<AnyType> {
        public AnyType data;
        public AvlNode<AnyType> left;
        public AvlNode<AnyType> right;
        public int hight;

        public AvlNode(AnyType d,AvlNode<AnyType> lt,AvlNode<AnyType> rt,int h){
            this.data=d;
            this.left=lt;
            this.right=rt;
            this.hight=h;
        }
    }

    public AvlNode<AnyType> root;
    public final int INBALANCE=1;

    public AvlTree(AnyType data){
        root=new AvlNode(data, null, null, 0);
    }

    public AvlNode<AnyType> insert(AnyType x){
        return insert(x, root);
    } 

    public AvlNode<AnyType> remove(AnyType x){
        return remove(x, root);
    } 

    private AvlNode<AnyType> insert(AnyType x,AvlNode<AnyType> t){
        if(t==null){
            return new AvlNode(x, null, null, 0);
        }
        var comparedResult=x.compareTo(t.data);
        if(comparedResult<0){
            t.left=insert(x, t.left);
        } else if(comparedResult>0){
            t.right=insert(x, t.right);
        } else{
            ;
        }
        return balance(t);
    }

    private AvlNode<AnyType> remove(AnyType x,AvlNode<AnyType> t){
        if(t==null){
            return new AvlNode(x, null, null, 0);
        }
        var comparedResult=x.compareTo(t.data);
        if(comparedResult<0){
            t.left=remove(x, t.left);
        } else if(comparedResult>0){
            t.right=remove(x, t.right);
        } else{
            ;
        }
        return balance(t);
    }

    private AvlNode<AnyType> balance(AvlNode<AnyType> t){
        if(t.left.hight-t.right.hight>INBALANCE){
            return rotateWithLeftChild(t);
        } else {
            return rotateWithRightChild(t);
        }
    }

    private AvlNode<AnyType> rotateWithLeftChild(AvlNode<AnyType> k2){
        var k1=k2.left;
        k2.left=k1.right;
        k2.right=k1;
        k1.hight=Math.max(k1.left.hight, k1.right.hight)+1;
        k2.hight=Math.max(k2.left.hight, k2.right.hight)+1;
        return k1;
    }

    private AvlNode<AnyType> doubleWithLeftChild(AvlNode<AnyType> k3){
        k3.left=rotateWithRightChild(k3.left);
        return rotateWithLeftChild(k3);
    }
    private AvlNode<AnyType> rotateWithRightChild(AvlNode<AnyType> k2){
        var k1=k2.right;
        k2.right=k1.left;
        k1.hight=Math.max(k1.left.hight, k1.right.hight)+1;
        k2.hight=Math.max(k2.left.hight, k2.right.hight)+1;
        return k1;
    }

    private AvlNode<AnyType> doubleWithRightChild(AvlNode<AnyType> k3){
        k3.right=rotateWithLeftChild(k3.right);
        return rotateWithRightChild(k3);
    }
}
